package Medium;

public class LC0162 {
    /**
     * 设计时间复杂度为logN的算法，这是使用二分查找的强暗示。一种直接的思想是，对于目前考察的元素mid，如果左侧/右侧元素比它更大，
     * 那么就往左侧/右侧继续搜寻。
     * 可以证明这种解法是正确的，详见https://leetcode.cn/problems/find-peak-element/solutions/998441/gong-shui-san-xie-noxiang-xin-ke-xue-xi-qva7v。
     */
    public static int findPeakElement(int[] nums) {
        int n = nums.length;
        if (n == 1) return 0;
        else if (n == 2) return nums[0] > nums[1] ? 0 : 1;

        int left = 0, right = n, mid;
        while (left < right) {
            mid = (int) (((long) left + right) / 2);
            int leftVal = mid - 1 >= 0 ? nums[mid - 1] : Integer.MIN_VALUE, rightVal = mid + 1 < n ? nums[mid + 1] : Integer.MIN_VALUE;
            if (leftVal < nums[mid] && nums[mid] > rightVal) return mid;
            else {
                if (nums[mid - 1] > nums[mid]) right = mid;
                else if (nums[mid + 1] > nums[mid]) left = mid + 1;
                // 题目保证相邻元素不相等
            }
        }

        return -1; // 输入可以保证不会到达此位置
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3, 4, 3};
        System.out.println(findPeakElement(nums));
    }
}
